<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 完成比赛的最少时间 -->
    <script>
      function minimumFinishTime(tires, changeTime, numLaps) {
        // one[i]: 使用同一个轮胎跑i圈的最短时间
        // 多跑一圈的时间<=重新换胎跑一圈的时间 估计一下最多一次跑19圈左右
        let one = new Array(20).fill(Infinity)
        for (let [f, r] of tires) {
          for (let i = 1, cost = 0; f * r ** (i - 1) <= f + changeTime; i++) {
            cost += f * r ** (i - 1)
            one[i] = Math.min(one[i], cost)
          }
        }
        // dp[i]: 可换胎跑i圈的最短时间
        let dp = new Array(numLaps + 1).fill(Infinity)
        dp[0] = 0
        for (let i = 1; i <= numLaps; i++) {
          // 最多跑19圈
          for (let j = 1, loops = Math.min(i, 19); j <= loops; j++) {
            dp[i] = Math.min(dp[i], dp[i - j] + changeTime + one[j])
          }
        }
        return dp[numLaps] - changeTime
      }
      console.log(
        minimumFinishTime(
          [
            [2, 3],
            [3, 4]
          ],
          5,
          4
        )
      )
    </script>
  </body>
</html>
